package 动态规划.状态压缩dp;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/22 16:02
 */
public class leetcode464CanIWin {
    /*
      有点类似于 博弈论那个味道了
      但是又不太一样
      注意状态压缩会有哪些特征！
      ①: 一般数据范围会比较小
      ②: int 32 bit 位 或者 long 64 bit 位 描述 完整的一些状态
     */


    // 先写一个 不用状态压缩的
    public boolean canIWin0(int n,int total){
        int nums [] = new int[n + 1];
        for(int i = 0;i < n;i++)
            nums[i] = i + 1;

        return recursion(nums,total);
    }
    public boolean recursion(int nums[],int rest){
        if(rest <= 0)
            return false;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == -1)
                continue;
            int cur = nums[i];
            nums[i] = -1;
            boolean flag = recursion(nums,rest - cur);
            nums[i] = cur;
            /*
              flag = false; 表示 recursion(nums,rest - cur);为false
              而 recursion(nums,rect - cur);表示的后手的结果,后手false 那当前层的 递归不就赢了嘛
              可能有点绕,在纸上 画一下就明白了,确实有点绕
                int cur = nums[i];
            nums[i] = -1;
             if( !recursion(nums,rest - cur))
                    return true;
             nums[i] = cur;
             上面这样写是错误的! 看着 挺正确 的其实是错误的! 这个得需要在纸上进行,分析一下!
             因为 先手 和 后手 都是绝顶聪明的!
             */
            if(!flag)
                return true;
        }
        return false;
    }

    /*
     上面得代码 再标记 1 ~ n 元素使用情况时,采用的 是数组 标记 -1
     当然也可以直接用一个 boolean flag [] 来标记
     但是这种标记 的问题就在于 引入了 一个 数组 变量参数 (参数的变化类型 突破了 整数 ),这怎么写 记忆化搜索 和 dp
     确实是个问题
     所以 引入下面这个 bit 位 标记的方式
     这样的话 可以 二维 dp 缓存表进行记忆化 搜索
     或者直接 dp
     */
    public boolean recursion(int status,int n,int rest){
        if(rest <= 0 )
            return false;
        // 1 ~ n 开始枚举 能不能赢
        for(int i = 1;i <= n;i++){
            // if has choosed
            if((status & (1 << i)) != 0)
                continue;
            // has no choosed ,then choosed and flag
            // 注意 这里 直接把两步 操作都做了, ①:标记 位使用过, 和 ②:回溯 ,(整数可以这样做,引用数据变量就不行了)
            if(!recursion(status | (1 << i),n,rest - i))
                return true;
        }
        return false;
    }

    /*
        记忆化搜索
        这个递归  没办法 改成 完全体的 dp（不现实）
        爆内存
     */
    public boolean solution(int n,int total){
        int dp[][] = new int[1 << (n + 1)][total + 1];
        return recursion(0,n,total,dp);
    }
    public boolean recursion(int status ,int n,int rest,int dp[][]){
        if(rest <= 0)
            return false;
        if(dp[status][rest] != 0)
            return dp[status][rest] == 1 ? true : false;
        boolean ans = false;
        for(int i = 1;i <= n;i++){
            if((status & (1 << i)) != 0)
                continue;
            if(!recursion(status | (1 << i),n,rest - i,dp)){
                ans = true;
                break;
            }
        }
        dp[status][rest] = ans ? 1 : -1;
        return ans;
    }

    /*
      用一个 status 可以 表示 很多的东西 ①： 哪些 数字已经使用过， ② 使用过的数字的和
      这样的话就不用开一个 二维数组了！
     */
    public boolean solutionFinal(int n,int total){
        int dp[] = new int[1 << (n + 1)];
        return recursion(0,n,total,dp);
    }
    public boolean recursion(int status ,int n,int rest,int dp[]){
        if(rest <= 0)
            return false;
        if(dp[status] != 0)
            return dp[status] == 1 ? true : false;

        for(int i = 1;i <= n;i++){
            if((status & (1 << i)) != 0)
                continue;
            if(!recursion(status | (1 << i),n,rest - i,dp)){
                dp[status] = 1;
                return true;
            }
        }
        dp[status] = -1;
        return false;
    }



    /*
      这是目前最快的代码
     */
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if(desiredTotal <= maxChoosableInteger) return true;
        if(maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        int total = desiredTotal, num = maxChoosableInteger;
        int[] dp = new int[1 << num];
        return dfs(dp, 0, total, num);
    }

    private  boolean dfs(int[] dp, int state, int total, int num){
        if(total <= 0) return false;
        if(dp[state] != 0) return dp[state] == 1;
        for(int i = 0; i < num; i ++){
            if((state & (1 << i)) > 0) continue;
            if(!dfs(dp, state | (1 << i), total - (i + 1), num)){
                dp[state] = 1;
                return true;
            }
        }
        dp[state] = -1;
        return false;
    }

}
